package com.test.daily.leetcode.y2022.m05.day0519.v08;

import java.util.Arrays;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/5/20 下午 11:06
 * @version: 1.0
 */
public class Solution {
    // 1. 先按照start排好序
    // 2.取出end之後，再二分查找
    public int[] findRightInterval(int[][] intervals) {
        int N = intervals.length;
        int[] ans = new int[N];
        int start[][] = new int[N][2];
        for (int i = 0; i < N; i++) {
            start[i][0] = intervals[i][0];
            start[i][1] = i;
        }
        Arrays.sort(start,(o1, o2) -> o1[0] - o2[0]);
        for (int i = 0; i < N; i++) {
            ans[i] = search(start, intervals[i][1]);
        }
        return ans;
    }
    public int search(int[][] start, int target){
        int left = 0;
        int right = start.length - 1;
        int idx = -1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(start[mid][0] >= target){
                idx = start[mid][1];
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return idx;
    }
}
